package 栈和队列.每日温度;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/2/22 16:45
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        int[] array = {1,2,3,4,5,4,3,2,1};
        int[] ints = dailyTemperatures(array);
        System.out.println(ints);
    }

    //单调栈
    public static int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] ans = new int[length];
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < length; i++) {
            //下标i每次会走在栈的前面一个和栈顶内容进行比较
            //栈中存放的是数组中每个数组的下标
            int temperature = temperatures[i];
            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                ans[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        return ans;
    }

    public static int[] test2(int[] array) {
        int length = array.length;
        int[] res = new int[length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < length; i++) {
            int tmp = array[i];
            while (!stack.isEmpty() && tmp > array[stack.peek()]) {
                Integer pre = stack.pop();
                res[pre] = i - pre;
            }
            stack.push(i);
        }
        return res;
    }


}
